623. 在二叉树中增加一行

#leetcode/tree/traversal

623. 在二叉树中增加一行

Similar Question

leading to the advanced question

Solution Tips

方案一: BFS

var addOneRow = function(root, val, depth) {
    // 用层次遍历做一次 depth 的题目吧
    let d = -1;
    // 因为有可能需要在 root 增加父亲, 因此来个哑节点
    const dummy = new TreeNode(0);
    dummy.left = root;
    const queue = [dummy];


    while (queue.length) {
        const n = queue.length;
        d++;

        for (let i = 0; i < n; i++) {
            const node = queue.pop();

            if (d === depth) {
                const newLeft = new TreeNode(val);
                const newRight = new TreeNode(val);

                const oldLeft = node.left;
                const oldRight = node.right;

                node.left = newLeft;
                newLeft.left = oldLeft;

                node.right = newRight;
                newRight.right = oldRight;
            }

            // 正常的层次遍历
            if (node.right) queue.push(node.right);
            if (node.left) queue.push(node.left);
        }

        if (d === depth) {
            // 增加完一层就可以直接结束了
            return dummy.left;
        }
    }
};

方案二: DFS

var addOneRow = function(root, val, depth) {
    if (!root) {
        return null;
    }
    if (depth === 1) {
        return new TreeNode(val, root, null);
    }
    if (depth === 2) {
        root.left = new TreeNode(val, root.left, null);
        root.right = new TreeNode(val, null, root.right);
    } else {
        root.left = addOneRow(root.left, val, depth - 1);
        root.right = addOneRow(root.right, val, depth - 1);
    }
    return root;
};